package com.wu.leetcode.leetcode560;

import java.util.HashMap;

/**
 * Leetcode560-和为K的子数组
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 */
class Solution {
    public int subarraySum(int[] nums, int k) {
        //方法一
        /*int len = nums.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                if (sum == k){
                    count++;
                }
            }
        }
        return count;*/
        //方法二：前缀和
        /*int count = 0;
        int length = nums.length;
        //前缀和
        int[] preSum = new int[length + 1];
        preSum[0] = 0;
        for (int i = 0; i < length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (preSum[j +1] - preSum[i]== k){
                    count++;
                }
            }
        }
        return count;*/
        //方法三：前缀和 + 哈希表优化
        //key:前缀和，value：对应的前缀和的个数
        HashMap<Integer, Integer> map = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        map.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (map.containsKey(preSum - k)){
                count += map.get(preSum - k);
            }
            //维护map
            map.put(preSum,map.getOrDefault(preSum,0) + 1);
        }
        return count;
    }
}